In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule. Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Biolodzy zajmujący się genetyką porównawczą poszukują sekwencji genów zachowanych w pewnym zbiorze gatunków.
Niech zbiór liczb oznacza geny - każdej liczbie odpowiada jeden gen.
Każdy z gatunków określony jest permutacją liczb , która oznacza uporządkowanie jego genów.
Ciąg genów jest zachowaną sekwencją genów w zbiorze gatunków, jeśli jest on podciągiem (niekoniecznie spójnym)
uporządkowania genów każdego z tych gatunków.
Zadanie
Napisz program, który:
wczyta ze standardowego wejścia opis sekwencji genów,
wyznaczy długość najdłuższej zachowanej sekwencji,
zapisze odpowiedź na standardowe wyjście.
Wejście
W pierwszej linii standardowego wejścia znajdują się dwie liczby całkowite i oddzielone pojedynczym odstępem,
przy czym oraz . Liczba oznacza liczbę genów, a liczbę gatunków.
Każda z następnych linii zawiera genom kolejnego gatunku zapisany jako permutacja liczb pooddzielanych pojedynczymi odstępami.
Wyjście
Na wyjściu powinna zostać wypisana dokładnie jedna liczba całkowita równa długości najdłuższej zachowanej sekwencji genów.
Przykład
Dla danych wejściowych:
5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4
poprawną odpowiedzią jest:
3
Wyjaśnienie
Podciągi:
są zachowanymi sekwencjami genów wśród tych 3 gatunków. Najdłuższą zachowaną sekwencją genów
tych 3 gatunków jest .